\documentclass[11pt]{article}
\usepackage{amsmath,amssymb,amsthm,epsfig}
\usepackage[left=1in,top=1in,right=1in,bottom=1in,nohead]{geometry}
%\usepackage{fullpage}
\usepackage{subfigure}
\usepackage{times}
\usepackage{url}

\begin{document}

\input{macros}


\title{Cobra-walks on Trees}


\author{Scott Roche}
\date{}
 
\maketitle


\section{Results on Arbitrary Trees}

Before we prove the general result, we need a few lemmas: 

\begin{lemma} Let $X,Y$ be two independent random variables. Let $W = \min(X,Y)$. Then the pdf of $W$, $p(w) \leq p(x) + p(y)$.  
\end{lemma} 
\begin{proof}
Clearly $\min(X,Y) \leq \max(X,Y)$. Take the c.d.f $P(W \leq k) = P(X \leq k)P(Y \leq k)$ by independence of $X,Y$.  Taking derivative w.r.t. $k$, we have $\frac{d}{dk} P(W \leq k) = p_x(k) P(Y \leq k) + p_y(k) P(X \leq k) \leq p_x(k) + p_y(k)$
\end{proof}

\begin{lemma}. Let $a_1,\ldots, a_d$ be a sequence of integers, with $\sum_i a_i = M$. Let $X$ and $Y$ be i.i.d random variables with distribution $\Pr(X = a_i) = \frac{1}{d}$. Then $E[\min(X,Y)] \leq \frac{M}{d}$. . 
\end{lemma}

\begin{proof}
Proof is by brute-force calculation
\begin{eqnarray*}
\Pr(\min(X,Y) = a_i) &=& \Pr(X =a_i, Y =a_i) + \Pr(X=a_i, Y > a_i) + \Pr(X > a_i, Y = a_i) \\
&=& \dfrac{1}{d^2} + 2 \dfrac{(d-i)}{d^2} = \dfrac{2(d-i) - 1}{d^2} 
\end{eqnarray*}
Thus we have: 
\begin{eqnarray*}
 E[\min(X,Y)] &=&  \sum_{i = 1}^d a_i \dfrac{2(d-i) -1}{d^2} = \frac{m}{d^2} (2d-1) - \frac{2}{d^2} \sum_i i a_i \\
 &=& \frac{1}{d} \frac{(m-2)}{d} \left[ 2d-1 - \sum_i i a_i \right] \\
 &\leq& \frac{m}{d}
\end{eqnarray*}
where the last inequality holds because $2d - 1 - \sum_i i a_i < d$.  
\end{proof}

We also need the following lemma:

\begin{lemma} \textbf{Matthew's Theorem for Cobra Walks}.  
Let $G$ be a connected graph on n vertices. Let $w$ be a cobra-walk on G starting at an arbitrary vertex. Then the cover-time of $w$ on $G$, $C(G)$,  is bounded from above by $h_{max} \ln n$. 
\end{lemma} 

\begin{proof}
We adopt the language of ~\cite{matthews}. Rather than viewing a cobra-walk as multiple pebbles moving over a graph, we will view it as a Markov process $M'$ of its own. In this process, the state space consists of $2^n$ states, each of which corresponds to a particular subset of the vertices that contain pebbles. Transitions between states occur with a probability equal to the probability of one particular pebble configuration in the original graph giving rise to the next state. 

We fix an initial position $a_0$ of $M'$ and a collection of $N$ Borel subsets of $M', \{A_1,\ldots, A_n\}$ to be visited. Here $A_i$ represents the set of all states of $M'$ in which vertex $i$ in $G$ contains a pebble. For any non-empty collection $\{A_1,\ldots,A_i\}$ of Borel subsets of $M'$ we then define $T(A_j) = \inf \{ t \geq 0 : X(t) \in A_j\}$ for $j = 1,\ldots, i$. That is, $T(A_j)$ is the smallest time t such that the walk $X$ on $M'$ visits a member of $A_j$. We also define $T(A_1,\ldots,A_i) = \max_{j = 1,\ldots,i} T(A_j)$. We now define:
\begin{equation*}
\mu_+ = \max_{i = 1, \ldots, N} \sup_{a \notin A_i} E_a T(A_i). 
\end{equation*} 
$\mu_+$ is $h_{max}$ in the standard language of random walks. Then from Theorem 2.6 of ~\cite{matthews}, 
\begin{equation*}
ET(A_1,\ldots,A_N) \leq \mu_+  \sum_{i=1}^{N} \frac{1}{i} 
\end{equation*}
thus proving the lemma. 
\end{proof}

\begin{lemma}
Let $T$ be a tree of size $M$. Pick a root, $r$, and let $r$ have $d$ children. Then a cobra-walk on $T$ starting at $r$ will have a return time to $r$ of $O(4M / d)$. 
\end{lemma}
\begin{proof}

To show that the Lemma holds for a cobra-walk, we will actually show that it holds for a simple random walk with transition probabilities modified to resemble those of a cobra-walk. For this simple random walk, we start at $r$ and in the first step pick one of the children of $r, r'$. Let $(d'+1)$ be the degree of $r'$. Then we define transition probabilities as follows: $p$ is the probability of returning to $r$ in the next step, and $p$ is the probability of continuing down the tree. They are given as:
\begin{eqnarray*}
p &=& \left(1 - \left( \dfrac{d'}{(d' +1)} \right)^2 \right) \\
q &=&  \left( \dfrac{d'}{(d' +1)} \right)^2 
\end{eqnarray*}
Note that these are the exact same probabilities that a cobra walk at vertex $r'$ would make. We will also "pre-compute" the value for $h_{r',r}$, the hitting time for a walk at child $r'$ of $r$. In this computation $T'$ is the subtree rooted at $r'$. It is:
\begin{eqnarray*}
h_{r',r} &\leq& p + q(r(T')  + h_{r',r} \\
\Rightarrow (1 - q) h_{r',r} &\leq& p + q r(T') \\
\Rightarrow h_{r',r} &\leq& 1 + \frac{q}{p} r(T') 
\end{eqnarray*}
Thus
\begin{eqnarray*}
\frac{q}{p} &=& \frac{d'^2}{2d' + 1} \\
\Rightarrow h_{r',r} &\leq&1 + \frac{d'^2}{2d' + 1}\left(\frac{3 |T|}{d} \frac{1}{d'} \right) \\
&\leq& 1 + \frac{3|T|}{2d} 
\end{eqnarray*}

The rest of the proof follows by mathematical induction. Consider a tree $T$ that has only two levels. Starting from $r$, the return time, 2, is constant, the relationship holds. For the inductive case, assume that the hypothesis holds. Then:
\begin{eqnarray*}
r(T) & \leq & 1+ \sum_{r' \in N(r)} p(r')h_{r',r} \\
&\leq& 1 + \frac{1}{d} \sum_{r' \in N(r)} h_{r',r} \\
&\leq& 1 + \frac{1}{d} \sum_{r' \in N(r)} \left(1 + \frac{d'^2}{2d' + 1} c \frac{|T'|}{d'}\right)\\
&\leq& 2 + \dfrac{c |T|}{2d} 
\end{eqnarray*}

Setting $c = 4$ gives us the result of the lemma for the simple random walk, and by stochastic dominance this holds also for the cobra walk. 

\end{proof}


Finally, have a lemma for the hitting time of a single step of a path along a tree. 
\begin{lemma}
Fix a path in a tree T made up of vertices $1,\ldots,l,l+1,\ldots, t$. Suppose a cobra-walk starts at vertex $l$ along the path. Then the expected time it takes for it to get to $l+1$ with at least one pebble is given by: 
\begin{equation}
h_{l,(l+1)}  = \frac{5}{4} + \frac{9}{5} \sum_{i = l}^{2} \left(\frac{1}{5}\right)^{l-i} |T_i|  
\end{equation}
where $T_l$ is the induced subtree formed by taking vertex $l$, its neighbors not on the path being traversed, and all of their descendants.  
\end{lemma}
\begin{proof}
Vertex $l$ is viewed through the context of having one edge to the vertex $l-1$, one edge to vertex $l$, and $d$ edges to some other vertices. Thus it can be viewed as the root of a tree,  and $T_l$ as the induced subgraph of $l$ and all vertices reached through its $d_l$ not-on-path children. We will need the following probabilities:
\begin{itemize}
\item  Probability of a pebble going from $l$ to $l+1 = p = \left(1 - \left(\dfrac{(d_l+1)}{(d_l+2)}\right)^2 \right)$
\item Probability of a pebble not going from $l$ to $l+1 = 1 - p = q$. 
\item Probability of a cobra walk sending both pebbles from $l$ to $l-1$ conditioned on it $not$ sending any pebbles from $l$ to $l+1 = q^{'}_l = \left(\dfrac{1}{(d_l+1)^2}\right)$ 
\item Probability of a cobra walk sending at least one pebble to the subtree $T_l$ conditioned on its not sending any pebbles to $l+1 = q^{''}_l = \left(\dfrac{(d_l)}{(d_l + 1)} \right)^2 + 2\left(\dfrac{d_l}{(d_l+1)^2}\right) = \dfrac{d_l^2 + 2d_l}{(d_l + 1)^2}$ 
\end{itemize}
Note that, conditioned on a pebble not advancing to vertex $l+1$, we actually have three disjoint events:  (A) Both pebbles go to $l-1$, (B) one pebble goes to $l-1$ and one pebbles goes into subtree $T_l$, and (C) both pebbles go into $T_l$. We define an alternate event $B'$, which is the event that one pebble goes down $T_l$ and nothing else happens (thus, it is not technically in the space of cobra-walk actions). If we let $R$ be the  time until first return of the cobra-walk to $l$ conditioned on no pebble going to $l+1$, we wish to show that $E[R|B] \leq E[R|B']$ and that $E[R|C] \leq E[R|B']$. What is the relationship between $B$ and $B'$? Consider two random variables, $X$ and $Y$, and let $X$ be the time until first return of a pebble that travels from $l$ to $l-1$, $Y$ be the time until first return of a pebble that travels into $T_l$. Then $R|B$ is just another random variable, $U = \min(X,Y)$. Since $U \leq Y$ over the entire space, $E[U] \leq E[Y]$, and clearly $R|B'$ is equivalent to Y. Thus $E[R|B] \leq E[R|B']$ By Lemma 4,  we also have that $E[R|B'] \geq E[R|C]$. Thus by the law of total expectation we have: 
\begin{eqnarray*}
E[R] &=& E[R|A]\Pr(A) + E[R|B]\Pr(B) + E[R|C]\Pr(C) \\
&\leq& E[R|A] \Pr(A)+ (\Pr(B) + \Pr(C))E[R|B'] \\
&=& E[R|A] \Pr(A) + E[R|B'](1 - \Pr(A)) 
\end{eqnarray*}

 Then the hitting time can be expressed as:  
\begin{eqnarray*}
h_{l,l+1} &\leq& p + q(E[R] + h_{l,l+1}) \\
\Rightarrow (1 - q) h_{l,l+1} &\leq& p + q(E[R]) \\
\Rightarrow h_{l,l+1} &\leq& 1 + \frac{q}{p} (q^{'}_l (1 + h_{l-1,l}) + q^{''}_l r(T_l)) 
\end{eqnarray*}
Note that $q/p = \frac{(d_l + 1)^2}{(2d_l + 3)}$. Since $r(T_l) \leq 4 |T_l| / d_l$ by the previous lemma, we continue with:
\begin{eqnarray*}
h_{l,l+1} &\leq& 1 + \frac{(d_l +1)^2}{(2d_l + 3)} \frac{1}{(d_l + 1)^2}(1 + h_{l-1,l}) +  \frac{(d_l +1)^2}{(2d_l + 3)} \frac{(d_l^2 + 2d_l)}{d_l + 1)^2} \frac{4 |T_l|}{d_l} \\
&\leq& 1 + \frac{1}{5} (1 + h_{l-1,l}) + \frac{12}{5} |T_l|  
\end{eqnarray*}
\end{proof}

If we expand the relation, we get:
\begin{eqnarray*}
h_{l,l+1} &\leq& \sum_{i = 0}^{l} \left(\frac{1}{5}\right)^i + \frac{9}{5} \left( |T_l| +  \left(\frac{1}{5}\right) |T_{l-1}| + \left(\frac{1}{5}\right)^2 |T_{l-2}| + \dots + \left(\frac{1}{5}\right)^{l-2} |T_{2}|\right) \\
h_{l,(l+1)} & \leq& \frac{5}{4} + \frac{12}{5} \sum_{i = l}^{2} \left(\frac{1}{5}\right)^{l-i} |T_i|  
\end{eqnarray*}

We are finally ready to prove our main theorem, that the cobra-walk cover time of an arbitrary tree occurs in $O(n \ln n)$ steps. 

\begin{theorem}
Let T be an arbitrary tree. Starting from any vertex of $T$, a cobra walk reaches the entire tree in $O(n \ln n)$ steps. 
\end{theorem}

\begin{proof}
By Matthew's Theorem for cobra-walks, $C(G) \leq (\ln n + o(1)) h_{max}$. We just need to prove that $h_{max}$ occurs in linear time.

Let $P$ be the path for which $h_{u,v}$ is maximized, and let the path consist of the sequence of vertices $1,2,\ldots,t$. As in the proof of the single-step hitting time, we note that for all but the first and last vertices on $P$, there is a subtree $T_l$ of size $|T_l|$ rooted at each vertex. Because $h_{1,l} \leq h_{1,2} + h_{2,3} + \ldots h_{t-1,t}$. Then, plugging from the single-step lemma, we have:
\begin{eqnarray*}
h_{1,t} &\leq& \frac{5}{4} t + \frac{12}{5} \sum_{j = 2}^{t-1}  \left[ |T_j| \sum_{i = 0}^{\infty} \left(\frac{1}{5}\right)^i \right] \\
&\leq& \frac{12}{5} t + \frac{12}{5}  \sum_{j=2}^{t-1} |T_j| \leq \frac{12}{5} n 
\end{eqnarray*} 
this proving our result. 
\end{proof}



\end{document}
